package algorithm.shipinke;

// import algorithm.leetcode.I1to200.OneSeven;

import java.util.Arrays;

/**
 * 各种排序
 */

public class Sort {

    public static int[] bubbleSort(int[] arr) {
        int len = arr.length;
        int exchangeTime = -1;
        while (exchangeTime != 0) {
            exchangeTime = 0;
            for (int i = 0; i < len-1; i++) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                    exchangeTime += 1;
                }
            }
        }
        return arr;
    }

    public void insertSort(int[] arr) {
        if (arr.length <= 1) return;

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) swap(arr, i, j);
            }
        }
    }


    public static void swap(int[] arr, int m, int n) {
        int temp = arr[m];
        arr[m] = arr[n];
        arr[n] = temp;
    }

    public void mergeSort(int[] arr, int begin, int end, int[] tmp) {
        if (begin < end) {
            int mid = (end - begin)/2 + begin;
            mergeSort(arr, begin, mid, tmp);
            mergeSort(arr, mid+1, end, tmp);
            merge(arr, begin, mid, end, tmp);
        }
    }

    public void merge(int[] arr, int begin, int mid, int end, int[] tmp) {
        int i = 0;
        int j = begin, k = mid+1;

        while (j <= mid && k <= end) {
            if (arr[j] > arr[k]) tmp[i++] = arr[k++];
            else tmp[i++] = arr[j++];
        }

        while (j <= mid) tmp[i++] = arr[j++];
        while (k <= mid) tmp[i++] = arr[k++];

        for (int l = 0; l < i; l++) {
            arr[begin+l] = tmp[l];
        }
    }


    public static void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) return;
        int mid = findPivot(arr, begin, end);
        quickSort(arr, begin, mid-1);
        quickSort(arr, mid+1, end);
    }

    public static int findPivot(int[] arr, int begin, int end) {
        while (begin < end) {
            while (begin < end && arr[begin] <= arr[end]) end--;
            swap(arr, begin, end);
            while (begin < end && arr[begin] <= arr[end]) begin++;
            swap(arr, begin, end);
        }
        return end;
    }


    /**
     * JDK Arrays.sort中实现的双轴快排简易实现
     * 由头尾两个轴点p1, p2将数组分为三段，小于等于p1的, p1到p2之间的, 大于p2的
     * 再递归地排序这三段
     * @param arr
     * @param begin
     * @param end
     */
    public static void dualPivotQuickSort(int[] arr, int begin, int end) {
        // 一些base case
        if (end <= begin) return;
        if (arr[end] < arr[begin]) swap(arr, begin, end);

        int pivot1 = arr[begin], pivot2 = arr[end];
        // (begin, left] 索引存储小于pivot1的值
        // [right, end) 索引存储大于pivot2的值
        // k从左向右遍历
        int left = begin, right = end, k = left+1;

        while (k < right) {
            // k指向元素比pivot1小
            if (arr[k] <= pivot1) swap(arr, ++left, k++);
            // k指向元素在pivot1和pivot2之间
            else if (arr[k] <= pivot2) k++;
            // k指向元素比pivot2大
            else {
                while (arr[right] >= pivot2) {
                    if (right-- == k) break;
                }
                if (k >= right) break;
                swap(arr, k, right);
            }
        }
        swap(arr, begin, left);
        swap(arr, end, right);
        dualPivotQuickSort(arr, begin, left-1);
        dualPivotQuickSort(arr, left+1, right-1);
        dualPivotQuickSort(arr, right+1, end);
    }


    public static void main(String[] args) {
       int[] arr = {23, 56, 1, 17, 35, 44, 32};
//         int[] arr = {1,3,3,3,7,2,4,5,3};

//        algorithm.shipinke.Sort os = new algorithm.shipinke.Sort();
        Sort.dualPivotQuickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }
}
